COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.device xgp
C00005 00003	.if false then begin "solutions"
C00007 ENDMK
C⊗;
.device xgp
.font 1 "basl30" <<text>>
.font 2 "bdr30" <<sym>>
.font 3 "basi30" <<var>>
.font 4 "basb30" <<bold>>
.evenleftborder←oddleftborder←1100;
.page frame 52 high 79 wide;
.area text lines 1 to 51 chars 1 to 79;
.place text;
.TURN ON "←%";
.NOFILL
←COMPUTER SCIENCE DEPARTMENT
←STANFORD UNIVERSITY



←CS 206         COMPUTING WITH SYMBOLIC EXPRESSIONS        FALL 1974
←MIDTERM EXAM

%1←Open Books and Notes




.FILL
	Write  LISP  functions  as  follows  using  the  M-expression
notation used in class:
.SKIP 2
1.	%3get%2[%3y, p%2]%1, where %3y%1 is an S-expression and %3p%1
is a list of A's and D's, is the subexpression of %3y%1 obtained from %3y%1
by taking %4car%1 and %4cdr%1 successively according to the elements of %3p%1.
Thus

	%3get%2[(A ((B) C) (B)), (D A A)] = (B).%1
.SKIP 2
2.	%3point%2[%3x, y%2] is a list of A's and D's such that
%3get%2[%3y, point%2[%3x, y%2]] is the left-most occurrence of the
S-expression %3x%1 in the S-expression %3y%1. Thus

	%3point%2[(B), (A ((B) C) (B))] = (D A A).%1
.SKIP 2
3.	%3allpoint%2[%3x, y%2]%1 is a list of all lists %3p%1 of A's
and D's such that %3get%2[%3y, p%2] = %3x%1.  Thus

	%3allpoint%2[(B), (A ((B) C) (B))] = ((D A A) (D D A)).%1
.SKIP 2
4.	Let a matrix be represented by a list of its rows and each row
by a list of its elements.  %3transpose u%1 is the transpose of the
matrix %3u%1, e.g.

	%3transpose %2((A B C) (D E F) (G H I)) = ((A D G) (B E H) (C F I)).%1
.SKIP 2
5.	Let a set be represented by a list %3u%1 of all its elements.
%3power u%1 is a list of %4all%1 the subsets of %3u%1.  Thus

	%3power %2(A B C) = (NIL (A) (B) (C) (A B) (A C) (B C) (A B C)).%1

I don't especially care about the order of the elements of %3power u%1.
.if false then begin "solutions"

(DEFPROP MIDFNS
 (NIL GETT POINT ALLPOINT TRANSPOSE POWER)
VALUE)

(DEFPROP GETT
 (LAMBDA (Y P) (COND ((NULL P) Y) ((EQ (CAR P) (QUOTE A)) (GETT (CAR Y) (CDR P))) (T (GETT (CDR Y) (CDR P)))))
EXPR)

(DEFPROP POINT
 (LAMBDA(X Y)
  (COND	((EQUAL X Y) NIL)
	((ATOM Y) (QUOTE FAIL))
	(T
	 ((LAMBDA(U)
	   (COND ((EQ U (QUOTE FAIL))
		  ((LAMBDA (V) (COND ((EQ V (QUOTE FAIL)) (QUOTE FAIL)) (T (CONS (QUOTE D) V))))
		   (POINT X (CDR Y))))
		 (T (CONS (QUOTE A) U))))
	  (POINT X (CAR Y))))))
EXPR)

(DEFPROP ALLPOINT
 (LAMBDA(X Y)
  (COND	((EQUAL X Y) (QUOTE (NIL)))
	((ATOM Y) NIL)
	(T
	 (APPEND (MAPCAR (FUNCTION (LAMBDA (W) (CONS (QUOTE A) W))) (ALLPOINT X (CAR Y)))
		 (MAPCAR (FUNCTION (LAMBDA (W) (CONS (QUOTE D) W))) (ALLPOINT X (CDR Y)))))))
EXPR)

(DEFPROP TRANSPOSE
 (LAMBDA(U)
  (COND ((NULL (CAR U)) NIL) (T (CONS (MAPCAR (FUNCTION CAR) U) (TRANSPOSE (MAPCAR (FUNCTION CDR) U))))))
EXPR)

(DEFPROP POWER
 (LAMBDA(U)
  (COND	((NULL U) (QUOTE (NIL)))
	(T ((LAMBDA (W) (APPEND W (MAPCAR (FUNCTION (LAMBDA (X) (CONS (CAR U) X))) W))) (POWER (CDR U))))))
EXPR)

.end "solutions"